A pseudorandom sequence is a sequence which, although produced deterministically, is impossible to distinguish, at least in a “reasonable” length of time, from a sequence of symbols in which each symbol is chosen entirely at random within the alphabet (what is meant by a length of time that is “reasonable” is obviously linked to the intended application and to the available computation power). In practice, a pseudorandom sequence is usually produced by initializing an appropriate algorithm by means of a secret parameter (called a “seed” or “key”, depending on the context), and where appropriate an additional parameter, secret or not, called the “initialization vector”.
The alphabet referred to above can be the binary set {0, 1}, for example, or the set of digits from 0 to 9, or the alphanumeric set comprising the digits and the uppercase and lowercase letters. In the context of the present invention, it is assumed that the symbols of the alphabet belong to a finite body (or “Galois body” GF(q)) K of cardinal q≧2.
An important application of pseudorandom sequences is “stream encryption”. This technique encrypts (in the cryptographic sense) a sequence {xi} of data in clear (indexed by i), with values in the alphabet, by means of another series {zi} of values in the same alphabet, where {zi} is precisely the sequence produced by a pseudorandom generator, to obtain an encrypted sequence {yi}, also with values in the alphabet. In other words, a composition law yi=xi*zi internal to the alphabet is chosen; for example, that internal law can be “exclusive OR” if the alphabet is the binary alphabet {0, 1}. Stream encryption is also called “on the fly” encryption because the items of data are encrypted one by one—as opposed to encryption methods using blocks of data. Compared to block encryption, stream encryption has the advantage of reducing transmission delay and data storage problems, but obviously requires a pseudorandom symbol data rate at least as high as the data rate of the data in clear; the application to stream encryption is therefore reserved to relatively fast pseudorandom sequence generators.
Stream encryption is used in particular in the Internet exchange protection protocol called Transport Layer Security (TLS) (see the paper by T. Dierks and C. Allen, “The TLS Protocol, version 1.0, RFC 2246”, Jan. 1999), one of the most widely used encryption algorithms of which is the RC4 algorithm (see the paper by J. D. Golic, “Linear Statistical Weakness of Alleged RC4 Keystream Generator”, Proceedings of Advances in Cryptology—EUROCRYPT '97, pages 226 to 238, editor W. Fumy, Lecture Notes in Computer Science vol. 1233, Springer-Verlag), and to encrypt traffic and signaling on the GSM radio channel by means of algorithms the most widely used of which is the A5/1 algorithm (see the paper by A. Biryukov, A. Shamir, and D. Wagner, “Real Time Cryptanalysis of A5/1 on a PC”, Proceedings of FSE 2000, pages 1 to 18, editor B. Schneier, Springer-Verlag 2000).
There are other important applications of pseudorandom sequences, for example in stochastic calculation and in public key authentication cryptographic protocols.
Many current stream algorithms, for example the A5/1 algorithm mentioned above, use recurrent linear sequences produced by linear feedback registers, possibly combined by means of non-linear functions (see the article by A. Canteaut, “Le chiffrement à la volée” [“On the fly encryption”], special issue of the magazine “Pour la Science”, pages 86 and 87, Paris, Jul.-Oct. 2002).
Now, none of the known pseudorandom sequence production methods is entirely satisfactory in reconciling the following two conditions:
1) the existence of strong security arguments, in which great confidence can be placed in the practical impossibility of distinguishing the pseudorandom sequences produced from perfectly random sequences; and
2) efficiency, i.e. the use of minimum calculation resources (time, memory, and so on) for each symbol of the sequence produced.
In fact, the first condition requires that the solidity of the generator be founded as directly as possible on the difficulty of a clearly identified mathematical problem considered to be difficult. Algorithms satisfying this first condition are known, for example the Blum-Micali algorithm (see the paper by M. Blum and S. Micali, “How to generate cryptographically strong sequences of pseudo-random bits”, J. Computing, vol. 13, no. 4, pages 850 to 863, Nov. 1984), which relies on the difficulty of the discrete logarithm problem, or the Blum-Blum-Shub algorithm (see the paper by L. Blum, M. Blum, and M. Shub, “A simple secure unpredictable pseudorandom number generator”, J. Computing, vol. 15, pages 364 to 383, 1986) which relies on the difficulty of the factorization problem, but these two algorithms (and more generally all algorithms in this category) have a much lower efficiency than the fastest current algorithms, for example the RC4 algorithm mentioned above. This is why no known pseudorandom generator having strong security arguments (i.e. for which it can be shown that the success of an attack against the generator involves the capacity to solve a reputedly difficult mathematical problem) is used at present on an industrial scale.
Conversely, the security of the fastest known pseudorandom sequence generators, such as the RC4 algorithm, or certain generators using linear feedback registers, such as Snow 2 (see the paper by P. Ekdahl and T. Johansson, “A new version of the stream cipher Snow”, Proceedings of Selected Areas in Cryptography 2002, pages 47 to 61, K. Nyberg and H. M. Heys editors, Springer-Verlag 2002), does not rely on the difficulty of clearly identified mathematical problems considered to be difficult. This results in potentially weak security: in the past, attacks have been discovered aimed at a number of generators in this category; thus the attack against the WEP encryption algorithm (a variant of the RC4 algorithm) used in the IEEE 802.11 system (better known as WiFi), discovered in 2001 by S. Fluhrer, I. Mantin, and A. Shamir (see the paper “Weaknesses in the Key Scheduling Algorithm of RC4”, Proceedings of Selected Areas in Cryptography 2001, Springer-Verlag) represents a spectacular example of the possible consequences of the absence of strong security arguments.